package com.demo.java.OD551_600.OD559;

import java.util.Scanner;
import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最小传输时延I(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146535428
 */
public class OdMain {
    public static void main(String[] args) {
        // 输入读取
        Scanner in = new Scanner(System.in);

        // 读取节点数n和边数m
        int n = in.nextInt();
        int m = in.nextInt();

        // 创建一个二维数组来存储图的边，matrix[i][0]为起点，matrix[i][1]为终点，matrix[i][2]为权重
        int[][] matrix = new int[m][3];
        for (int i = 0; i < m; i++) {
            matrix[i][0] = in.nextInt(); // 起点
            matrix[i][1] = in.nextInt(); // 终点
            matrix[i][2] = in.nextInt(); // 权重
        }

        // 读取起始节点和目标节点
        int start = in.nextInt();
        int end = in.nextInt();

        // 优先队列实现Dijkstra算法，队列按路径长度从小到大排列
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        // dist数组用于存储从起点到每个节点的最短距离，初始化为无穷大
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0; // 起点到自己的距离为0
        queue.add(new int[]{start, 0}); // 将起点加入队列

        // Dijkstra算法主循环
        while (!queue.isEmpty()) {
            int[] poll = queue.poll(); // 获取队列中距离最小的节点
            int node = poll[0]; // 当前节点
            // 遍历所有的边
            for (int i = 0; i < matrix.length; i++) {
                if (matrix[i][0] == node) { // 找到当前节点的邻接边
                    int next = matrix[i][1]; // 终点
                    // 判断是否通过当前节点可以得到更短的路径
                    if (dist[next] > dist[node] + matrix[i][2]) {
                        dist[next] = dist[node] + matrix[i][2]; // 更新距离
                        queue.add(new int[]{next, dist[next]}); // 将更新后的节点加入队列
                    }
                }
            }
        }

        // 输出结果，如果目标节点的距离还是无穷大，表示不可达，返回-1
        if (dist[end] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(dist[end]); // 输出最短路径
        }
    }
}